/*
 *  linux/kernel/sched.c
 *
 *  (C) 1991  Linus Torvalds
 */

/*
 * 'sched.c' is the main kernel file. It contains scheduling primitives
 * (sleep_on, wakeup, schedule etc) as well as a number of simple system
 * call functions (type getpid(), which just extracts a field from
 * current-task
 */
#include <linux/sched.h>
#include <linux/kernel.h>
#include <linux/sys.h>
#include <linux/fdreg.h>
#include <asm/system.h>
#include <asm/io.h>
#include <asm/segment.h>

#include <signal.h>

#define _S(nr) (1<<((nr)-1))
#define _BLOCKABLE (~(_S(SIGKILL) | _S(SIGSTOP)))

// 显示进程的信息
void show_task(int nr,struct task_struct * p)
{
	// task结构和特权级0的栈共用同一空间，下面是将j计数成栈的字节数量
	int i,j = 4096-sizeof(struct task_struct);

	// 打印进程的索引号，pid，状态值
	printk("%d: pid=%d, state=%d, ",nr,p->pid,p->state);

	// 统计栈中不为0的数量，如果为0表示该单元已经使用过
	// 也就是说这里通过统计不为0的值，来计算栈有多少还是是空闲的
	// 统计是，从栈底开始统计，向上检查，遇到为0时 退出
	i=0;
	while (i<j && !((char *)(p+1))[i])	// (p+1)刚好指向下一个task结构，即当前task的末尾，栈底的位置
		i++;

	// 显示有多少个空闲单元未用
	printk("%d (of %d) chars free in kernel stack\n\r",i,j);
}

// 遍历所有的进程表，显示进程信息
// 当按下F1、F2这些功能键时显示进程列表的信息
void show_stat(void)
{
	int i;

	// 遍历进程表
	for (i=0;i<NR_TASKS;i++)
		if (task[i])
			// 显示进程信息
			show_task(i,task[i]);
}

#define LATCH (1193180/HZ)		// 系统时钟节拍计数

extern void mem_use(void);

extern int timer_interrupt(void);
extern int system_call(void);

// 任务结构，将task与stack结合
// 即分配一页内存，低端用于task结构，高端用于特权级0的栈。这样栈的大小实际有些受限
union task_union {
	struct task_struct task;	// 任务结构
	char stack[PAGE_SIZE];		// 4KB 特权级0时用的栈
};

// 初始任务，直接给出了初始化的值，没有定义额外的函数进行配置
// 这样避免了动态分配。因为初始任务是固定的，所以直接静态分配更加简单一些
// 下面这里实际上是分配了4KB的静态变量，并对task域进行初始化
static union task_union init_task = {INIT_TASK,};   

long volatile jiffies=0;		// 系统节拍计数，在每次定时中kontimer_interrupt中增+1，用于系统定时
long startup_time=0;			// 1970-1-1 0时的秒数

// 初始化时，当前进程是init_task
struct task_struct *current = &(init_task.task);
struct task_struct *last_task_used_math = NULL;

// 进程指针表，第0个进程是固定的，init_task
struct task_struct * task[NR_TASKS] = {&(init_task.task), };

// 进程0的栈空间配置，会被用来在head.s中加载，用做初始化的栈空间，以及特权级3的栈空间
long user_stack [ PAGE_SIZE>>2 ] ;		// 进程0的内核栈只有4KB
struct {
	long * a;			// user_stack的末端地址，即栈的起始
	short b;			// 所在的段选择子
} stack_start = { & user_stack [PAGE_SIZE>>2] , 0x10 };

/*
 *  'math_state_restore()' saves the current math information in the
 * old math state array, and gets the new ones from the current task
 */
void math_state_restore()
{
	if (last_task_used_math == current)
		return;
	__asm__ __volatile__("fwait");
	if (last_task_used_math) {
		__asm__ __volatile__("fnsave %0"::"m" (last_task_used_math->tss.i387));
	}
	last_task_used_math=current;
	if (current->used_math) {
		__asm__ __volatile__("frstor %0"::"m" (current->tss.i387));
	} else {
		__asm__ __volatile__("fninit"::);
		current->used_math=1;
	}
}

/*
 *  'schedule()' is the scheduler function. This is GOOD CODE! There
 * probably won't be any reason to change this, as it should work well
 * in all circumstances (ie gives IO-bound processes good response etc).
 * The one thing you might take a look at is the signal-handler code here.
 *
 *   NOTE!!  Task 0 is the 'idle' task, which gets called when no other
 * tasks can run. It can not be killed, and it cannot sleep. The 'state'
 * information in task[0] is never used.
 */
void schedule(void)
{
	int i,next,c;
	struct task_struct ** p;

/* check alarm, wake up any interruptible tasks that have got a signal */
	// 警告时钟报警定时
	// 遍历扫描，进程0除外
	for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
		if (*p) {
			// 如果设置了alarm，且当前时间已经超过了报警时间，则要发SIGALRM信号给进程，通知时间已经到了
			if ((*p)->alarm && (*p)->alarm < jiffies) {
				(*p)->signal |= (1<<(SIGALRM-1));
				(*p)->alarm = 0;
			}
			
			// TODO: ???
			if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) && (*p)->state==TASK_INTERRUPTIBLE)
				(*p)->state=TASK_RUNNING;
		}

/* this is the scheduler proper: */

	// 死循环，直到找到一个可以运行的任务，并切换过去
	while (1) {
		c = -1;			// 任务执行时间计数
		next = 0;		// 下一个任务的索引号
		i = NR_TASKS;
		p = &task[NR_TASKS];

		// 从任务数组最后往前扫, 不包含对进程0的扫描
		while (--i) {
			// 跳过不含任务的项
			if (!*--p)
				continue;
			
			// 如果任务就绪或者可运行，且剩余执行时间>c，则将c进行更新，且next指向他
			if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
				c = (*p)->counter, next = i;
		}

		// 如果c不为0。有可能是>0的，此时即找到一个可以运行的任务。切换到下一个任务.
		// 也有可能c==-1, h此时，next的值为0，next=0不是错误，也可以传给switch_to进行处理
		if (c) break;

		// 到这里c应当是==0的，
		// 从尾往前扫，也避免扫第一个, TODO: ??
		for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
			// 如果任务有效，更新counter，优先级值更大的得到的counter越多，即运行时间越长
			if (*p)
				(*p)->counter = ((*p)->counter >> 1) +(*p)->priority;
	}

	// next可能指向某个任务号，或者为0。为0即表示进程0
	switch_to(next);
}

// 使调用进程(线程)进入休眠状态(就是挂起);直到接收到信号且信号函数成功返回
// 设置为current后，执行schedule就会切换到其它任务运行
// 对于进程0，没什么用处，只是简单的切换到其它任务，如果有的话
int sys_pause(void)
{
	// 设置状态为可中断的休眠状态
	current->state = TASK_INTERRUPTIBLE;

	// 进行一次任务调试操作
	schedule();
	return 0;
}

// 让进程在队列p上睡眠，用于与中断处理程序同步
void sleep_on(struct task_struct **p)
{
	struct task_struct *tmp;		// 相当于next指针

	// 无效值，退出
	if (!p)
		return;
	// 进程0是一直在运行的，不能进入sleep
	if (current == &(init_task.task))
		panic("task[0] trying to sleep");
	
	// 将自己插入表头
	tmp = *p;		// 队列头部的值，暂存到自己这里
	*p = current;	// 将自己插入到队列的头部

	// 设置不可中断的等待状态
	current->state = TASK_UNINTERRUPTIBLE;
	schedule();

	// 唤醒之后，将自己后一任务设置为TASK_RUNNING，可以运行
	// 当后一任务再恢复运行时，其再将后一任务恢复运行
	// 这样，就不是一次性将所有队列中的任务唤醒，而是由每个任务单独唤醒自己后面的一个
	if (tmp)
		tmp->state=0;
}

// 让进程在队列p上睡眠,切换至可中断状态，用于与中断处理程序同步
// TODO：区别？
void interruptible_sleep_on(struct task_struct **p)
{
	struct task_struct *tmp;		

	// 以下同上
	if (!p)
		return;
	if (current == &(init_task.task))
		panic("task[0] trying to sleep");
	tmp=*p;
	*p=current;

repeat:	
	// 设置状态，并切换
	current->state = TASK_INTERRUPTIBLE;
	schedule();

	// 醒来后，如果队列第一个任务不是自己，则将前一任务置为就绪态
	// 再将自己重新切换成睡眠状态，也就是说前面的任务先运行，自己最后运行？TODO: 为啥？
	if (*p && *p != current) {
		(**p).state=0;
		goto repeat;
	}

	// 同上
	if (tmp)
		tmp->state=0;
}

// 唤醒队列中的任务。内部只唤醒一个，多个任务由每个任务自己唤醒后面的任务
void wake_up(struct task_struct **p)
{
	// 只检查第一个是否有任务，有的话，设置成就绪状态
	if (p && *p) {
		(**p).state=0;

		// 队首清清空
		*p=NULL;
	}
}

/*
 * OK, here are some floppy things that shouldn't be in the kernel
 * proper. They are here because the floppy needs a timer, and this
 * was the easiest way of doing it.
 */
static struct task_struct * wait_motor[4] = {NULL,NULL,NULL,NULL};
static int  mon_timer[4]={0,0,0,0};
static int moff_timer[4]={0,0,0,0};
unsigned char current_DOR = 0x0C;

int ticks_to_floppy_on(unsigned int nr)
{
	extern unsigned char selected;
	unsigned char mask = 0x10 << nr;

	if (nr>3)
		panic("floppy_on: nr>3");
	moff_timer[nr]=10000;		/* 100 s = very big :-) */
	cli();				/* use floppy_off to turn it off */
	mask |= current_DOR;
	if (!selected) {
		mask &= 0xFC;
		mask |= nr;
	}
	if (mask != current_DOR) {
		outb(mask,FD_DOR);
		if ((mask ^ current_DOR) & 0xf0)
			mon_timer[nr] = HZ/2;
		else if (mon_timer[nr] < 2)
			mon_timer[nr] = 2;
		current_DOR = mask;
	}
	sti();
	return mon_timer[nr];
}

void floppy_on(unsigned int nr)
{
	cli();
	while (ticks_to_floppy_on(nr))
		sleep_on(nr+wait_motor);
	sti();
}

void floppy_off(unsigned int nr)
{
	moff_timer[nr]=3*HZ;
}

void do_floppy_timer(void)
{
	int i;
	unsigned char mask = 0x10;

	for (i=0 ; i<4 ; i++,mask <<= 1) {
		if (!(mask & current_DOR))
			continue;
		if (mon_timer[i]) {
			if (!--mon_timer[i])
				wake_up(i+wait_motor);
		} else if (!moff_timer[i]) {
			current_DOR &= ~mask;
			outb(current_DOR,FD_DOR);
		} else
			moff_timer[i]--;
	}
}

// 定时器列表
#define TIME_REQUESTS 64			// 定时器数量
static struct timer_list {
	long jiffies;			// 定时时间
	void (*fn)();			// 被调函数
	struct timer_list * next; // 后一定时器
} timer_list[TIME_REQUESTS], * next_timer = NULL;	// 定时器链表首结点


// 添加一个定时器：主要给软盘使用，应用进程用不了
void add_timer(long jiffies, void (*fn)(void))
{
	struct timer_list * p;

	// 参数合法检查
	if (!fn)
		return;

	// 关中断进行保护
	cli();

	// 时间为0，即立即到达时间，直接调用不用插入链表中
	if (jiffies <= 0)
		// 执行处理函数
		(fn)();
	else {
		// 遍历整个定时器
		for (p = timer_list ; p < timer_list + TIME_REQUESTS ; p++)
			// 找到空闲项
			if (!p->fn)
				break;
		
		// 找不到，报错
		if (p >= timer_list + TIME_REQUESTS)
			panic("No more time requests free");

		// 插入到表头
		p->fn = fn;
		p->jiffies = jiffies;
		p->next = next_timer;
		next_timer = p;
	
		// 如果有后续定时，且其延时比自己的小，则将自己插入到其后边，后一个在前边？
		// 中断的扫描，进行一个递减的排序，且每一个定时器的定时为前面所有时间的和
		while (p->next && p->next->jiffies < p->jiffies) {
			p->jiffies -= p->next->jiffies;		// 将自己延时减去前一个
			fn = p->fn;						// 交换前后的fn
			p->fn = p->next->fn;
			p->next->fn = fn;				// 前面的next指向自己

			jiffies = p->jiffies;			// 交换jiffies
			p->jiffies = p->next->jiffies;
			p->next->jiffies = jiffies;

			p = p->next;					// 继续扫描
		}
	}
	sti();
}

// 定时中断处理，在每次发生定时中断时被调用
// CPL为发生定时中断时，当前运行程序的权限
void do_timer(long cpl)
{
	extern int beepcount;
	extern void sysbeepstop(void);

	// 在显示控制台中，可能会发生蜂鸣器响，sysbeep 
	// 响的时间要持续一断时间，超过这个时间后就关掉
	if (beepcount)
		// 减到0后，就关掉定时器，也就是关掉蜂鸣器
		if (!--beepcount)
			sysbeepstop();

	// 统计任务有多长时间在执行用户程序，还有多长时间在执行内核程序
	if (cpl)
		// cpl != 0， 非内核级
		current->utime++;
	else	// ==0，特权级程序
		current->stime++;

	// 处理定时器
	if (next_timer) {
		// 减去定一个时钟节拍
		next_timer->jiffies--;

		// 如果值为0，则调用一下，释放掉定时器
		// 同时继续扫后面的，直到后面的时间值有一个不为0的
		while (next_timer && next_timer->jiffies <= 0) {
			void (*fn)(void);
			
			fn = next_timer->fn;
			next_timer->fn = NULL;
			next_timer = next_timer->next;
			(fn)();
		}
	}

	// 因为某种情况，关掉软盘
	if (current_DOR & 0xf0)
		do_floppy_timer();

	// 时间片的处理：减掉当前任务的时间片计数，如果不为0，即还有时间运行，则继续往下跑
	if ((--current->counter)>0) return;
	current->counter=0;

	// 时间片用完了
	// 如果特权级=0，即在执行内核程序时产生中断，直接退出
	if (!cpl) return;

	// 非内核程序，进行任务切换
	schedule();
}

// alarm()用来设置定时器。时间到了，就会向当前进程发送SIGALRM信号。
// 如果参数seconds 为0，则之前设置的闹钟会被取消，并将剩下的时间返回。
// 如果未设置信号SIGALARM的处理函数，那么alarm()默认处理终止进程。
int sys_alarm(long seconds)
{
	// 取老的值
	int old = current->alarm;

	// 如果有老的值，计算其秒数
	if (old)
		old = (old - jiffies) / HZ;

	// 设置发送alarm的时间，按启动的时钟节拍计算
	current->alarm = (seconds>0)?(jiffies+HZ*seconds):0;
	return (old);
}

// 获取进程的id
int sys_getpid(void)
{
	return current->pid;
}

// 获取进程的父id
int sys_getppid(void)
{
	return current->father;
}

// 取得执行目前进程的用户识别码, TODO: 用户身份
int sys_getuid(void)
{
	return current->uid;
}

// 取得执行目前进程有效的用户识别码
int sys_geteuid(void)
{
	return current->euid;
}

// 用来取得执行目前进程的组识别码,有效的用户识别码用来决定进程执行的权限
int sys_getgid(void)
{
	return current->gid;
}

// 取得执行目前进程有效组识别码. 有效的组识别码用来决定进程执行时组的权限.
int sys_getegid(void)
{
	return current->egid;
}

// 调用优先级
// 增加inc到当前进程的nice值。（nice值越大，运行的优先级越低）
int sys_nice(long increment)
{
	// 提高优先级，值越大，优先级越小。所以当inc为正数时，意思就是将优先级提升
	// 这样就意味着将优先级数值要变小，所以要减去increment
	if (current->priority-increment>0)
		current->priority -= increment;
	return 0;
}

// 初始化调度器

void sched_init(void)
{
	int i;
	struct desc_struct * p;

	// TODO: 大小必须为16字节
	if (sizeof(struct sigaction) != 16)
		panic("Struct sigaction MUST be 16 bytes");

	// 设置初始进程0的TSS描述符和LDT描述符
	set_tss_desc(gdt+FIRST_TSS_ENTRY,&(init_task.task.tss));  // 初始化TSS描述符, 对GDT第4表项设置
	set_ldt_desc(gdt+FIRST_LDT_ENTRY,&(init_task.task.ldt));  // 初始化LDT描述符，对GDT第5个表项进行了设置
	p = gdt+2+FIRST_TSS_ENTRY;   // 定位到下一个任务的表项，2-进程0占用的表项数量2个

	// 初始化其它的各个任务槽，然后将相应的GDT表项也进行清0。每个任务表项占用两个项目
	for(i=1;i<NR_TASKS;i++) {
		task[i] = NULL;
		p->a=p->b=0;
		p++;
		p->a=p->b=0;
		p++;
	}

/* Clear NT, so that we won't have troubles with that later on */
	// 修改EFLAGS中的NT标志位，具体原因未知
	__asm__ __volatile__("pushfl ; andl $0xffffbfff,(%esp) ; popfl");

	// 设置当前的任务TR寄存器为进程0的，LDT也是进程0的
	// 这样硬件就知道当前正在运行的是task0对应的进程了
	// 注意，下面0不代表在GDT中的索引，而是进程的序号，从0开始计算
	ltr(0);			// TR = 0x20，即第4个表项	
	lldt(0);		// LDT=0x28, 第5个表项

	// 配置定时器，设置每10秒周期性中断一次
	outb_p(0x36,0x43);		/* binary, mode 3, LSB/MSB, ch 0 */
	outb_p(LATCH & 0xff , 0x40);	/* LSB */
	outb(LATCH >> 8 , 0x40);	/* MSB */
	// 涉及到定时任务切换，所以在这里初始化中断服务程序
	set_intr_gate(0x20,&timer_interrupt);	// 设置定时中断，IDT中断号0x20
	outb(inb_p(0x21)&~0x01,0x21);	// 打开定时中断，取消屏蔽位

	// 设置系统调用的门：DPL=0的中断门，供系统调用 INT 0x80使用
	set_system_gate(0x80,&system_call);
}
